package com.zrkizzy.linkedlist;

/**
 * 206. 反转链表<br/>
 * https://leetcode.cn/problems/reverse-linked-list/
 * @author zhangrongkang
 * @date 2022/11/16
 */
public class 反转链表 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        // 递归到底时返回的node节点就是链表的最后一个节点，每一次返回的都是新链表的首节点
        // 每一次回溯时都将链表的节点顺序进行了互换，并不会形成环。
        // 因为第一次回溯时链表的尾节点的next就是null，同时每一次回溯时原来的尾节点的下一个节点就已经指向了前一个节点
        // 在回溯到最初状态时因为第一次递归时首节点的前一个节点就为null，因此最后一次回溯就将新链表的尾节点的next赋值为null
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            return recursion(null, head);
        }

        private ListNode recursion(ListNode pre, ListNode cur) {
            // 递归到底的情况
            if (cur == null) {
                // 如果当前节点为空，则将上一个节点进行返回
                return pre;
            }
            // 遍历下一个节点，接收返回的节点
            ListNode node = recursion(cur, cur.next);
            // 将当前链表进行反转
            cur.next = pre;
            return node;
        }
    }
}
